"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        """
        生成给定区域[(ltr, ltc), (rtr, rtc)]的子树
         @param ltr: 范围矩阵左上角行标
         @param ltc: 范围矩阵左上角列标
         @param rtr: 范围矩阵右下角行标
         @param rtc: 范围矩阵右下角列标
        """
        def construct_from_area(ltr: int, ltc: int, rbr: int, rbc: int) -> 'Node':
            # area_sum[(si, sj), (i,j)] = preSum[i+1][j+1] – preSum[si][j+1] – preSum[i+1][sj] + preSum[si][sj]
            area_sum = preSum[rbr+1][rbc+1] - preSum[ltr][rbc+1] - preSum[rbr+1][ltc] + preSum[ltr][ltc]    # 计算区域范围和
            area_cnts = (rbr - ltr + 1) * (rbc - ltc + 1)       # 计算区域单元格个数
            if area_sum == 0 or area_sum == area_cnts:
                # 如果区域和为0，则该区域全为0；如果区域和等于区域格子数，则区域全为1；这两种情况就是叶子节点
                return Node(area_sum // area_cnts, True)      
            mr = ltr + (rbr - ltr + 1) // 2     # 中间行的行号
            mc = ltc + (rbc - ltc + 1) // 2     # 中间列的列号
            # 将当前区域划分成四个子区域，递归生成子树
            return Node(False, False, 
                construct_from_area(ltr, ltc, mr - 1, mc - 1),
                construct_from_area(ltr, mc, mr - 1, rbc),
                construct_from_area(mr, ltc, rbr, mc - 1),
                construct_from_area(mr, mc, rbr, rbc))
        
        n = len(grid)            # 矩阵尺寸
        preSum = [[0] * (n + 1) for _ in range(n + 1)]     # 初始化前缀和数组
        # 计算二维矩阵前缀和
        for i, row in enumerate(grid):
            for j, value in enumerate(row):
                preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j] + value
        # 构造四叉树
        return construct_from_area(0 , 0, n-1, n-1)

        